package com.example.leetcode.c101_c200.c114;
/**
 * 给定一个二叉树，原地将它展开为一个单链表。
 *
 *  
 *
 * 例如，给定二叉树
 *
 *     1
 *    / \
 *   2   5
 *  / \   \
 * 3   4   6
 * 将其展开为：
 *
 * 1
 *  \
 *   2
 *    \
 *     3
 *      \
 *       4
 *        \
 *         5
 *          \
 *           6
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

import com.example.leetcode.common.TreeNode;
import com.example.leetcode.common.TreeNodeWrapper;

import java.util.LinkedList;

/**
 * 二叉树展开为链表
 * @author zhanpengguo
 * @date 2020/10/2 15:06
 */
public class Solution {

    LinkedList<Integer> list = new LinkedList<>();

    public void flatten(TreeNode root) {
        TreeNode node = root;
        preorder(root);
        list.poll();
        while (!list.isEmpty()) {
            node.right = new TreeNode(list.poll());
            node.left = null;
            node = node.right;
        }
    }

    private void preorder(TreeNode root) {
        if (root == null) {
            return;
        }
        list.add(root.val);
        preorder(root.left);
        preorder(root.right);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode root = TreeNodeWrapper.stringToTreeNode("[]");
        TreeNodeWrapper.prettyPrintTree(root);
        System.out.println();
        solution.flatten(root);
        TreeNodeWrapper.prettyPrintTree(root);
    }
}
